package xkp.lesson5;

/**
 * junit软件测试
 * @author Administrator
 *
 */
public class Demo1 {
	public static void main(String[] args) {
		int[] arr = {2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124,
					 2,4,6,21,567,12,543,321,
					 432,654,6,1234,345,5,23,
					 54,876,23,4,645,123,23,
					 345,435,534,534,235,432,42,43234,
					 23655,4756,3244,345,457,2334,
					 756,234,346,234,54667,456234,7876,
					 21414,68567445,12312,45645,86474,2352,57465,
					 234324,574674,324234,6785685,44,66,88,213123,
					 545,2,34542,213,213,2133,21,432,54,32,
					 543,5,43,6,43,653,6,54376,
					 547,65,7,657,65,7,65,765,7,65,765,7,65,7,213413234,456754,1231,322,
					 213123,6745,2341,8758,9,234,8987,547,1324124,657,123,67,5321,4576,354,74,23,159,
					 1058,24589,1248,123,876,1224,9068,134,67547,124
		};
		//上午讲述的内容有
		System.out.println(arr.length);
		//冒泡排序
		//获取当前系统时间，以毫秒为单位
		quickSort(arr, 0, arr.length-1);
		long beginTime = System.currentTimeMillis();
//		for(int i = 1; i <= 1000; i++) {
//			//21 17 18 19
//			//maopao(arr);
//			//14 22 18 因为里面有递归 
//			quickSort(arr, 0, arr.length-1);
//		}
		//二分查找数据量越大，优势越明显
		for(int i = 1; i <= 100000; i++) {
			//searchKey(arr, 68567445);
			binarySearch(arr, 68567445);
		}
		long endTime = System.currentTimeMillis();
		System.out.println(endTime-beginTime+":ms");
		//快速排序
		//普通查找
	
		//二分查找
		
		//需求：实际测试一下算法的执行效率
		
	}
	
	//冒泡
	/**
	 * 冒泡排序
	 * @param arr  需要被排序的数组
	 */
	public static int[] maopao(int[] arr) {
		//i是冒泡的个数
		for(int i = 0; i< arr.length-1; i++) {
			//每个泡要向上冒几次
			//arr.length-1是为了避免arr[j+1]越界
			//减i是为了提高效率，避免不需要的操作
			for(int j = 0; j < arr.length-1-i; j++) {
				if(arr[j]>arr[j+1]) {
					//此处直接操作原数组进行交换
					int temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}
			}
		}
		return arr;
		//冒泡排序后的结果需不需要返回
		//
	}
	//快速
	public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>=high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];
 
        while (i<j) {
            //先看右边，依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
 
        }
        //最后将基准为与i和j相等位置的数字交换
         arr[low] = arr[i];
         arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }
 
 
	
	//普通查找
	public static int searchKey(int[] arr,int value) {
		for(int i = 0; i < arr.length; i++) {
			if(arr[i] == value) {
				return i;
			}
		}
		return -1;
	}
	
	//二分查找
	public static int binarySearch(int[] arr,int key) {
        //定义三个索引位置。
        int min = 0;
        int max = arr.length - 1;
        int mid = 0;
        //循环折半，条件， min<=max
        while(min <= max) {
            //公式，计算中间索引
            mid = (min+max)/2;
            //让被找元素和中间索引元素进行比较
            if(key>arr[mid]) {
                min = mid +1;
            }else if(key <arr[mid]) {
                max = mid -1;
            }else {
                //找到元素，返回元素索引
                return mid;
            }
        }
        return -1;
    }

}
